package com.itheima.algorithm.recursion_single;

/**
 * 递归二分查找
 */
public class E03BinarySearch {

    public static int search(int[] a, int target) {
        return fn(a, target, 0, a.length - 1);
    }


    /**
     * <h3>递归(子问题)函数：查找 [i .. j] 范围内的目标</h3>
     *
     * @param a      数组
     * @param target 待查找值
     * @param left   起始索引
     * @param right  结束索引
     * @return <p>找到返回索引</p><p>找不到返回 -1</p>
     */
    public static int fn(int[] a, int target, int left, int right) {
        if (left > right) { //递归出口
            return -1;
        }

        int mid = (left + right) >>> 1;
        int midValue = a[mid];
        if (target < midValue) {//向左查找
            return fn(a, target, left, mid - 1);
        } else if (target > midValue) {
            return fn(a, target, mid + 1, right);
        } else {
            return mid;
        }
    }


}
